class Solution:
    def findMinHeightTrees(self, n: int, edges):
        if n == 1:
            return [0]
        tree = [set() for _ in range(n)]
        for i in range(len(edges)):
            edge = edges[i]
            tree[edge[0]].add(edge[1])
            tree[edge[1]].add(edge[0])

        # print(tree)

        maxIndex = 0
        maxLen = len(tree[0])
        for i in range(1, n):
            if len(tree[i]) > maxLen:
                maxLen = len(tree[i])
                maxIndex = i

        lineSegments = []
        newSe = [[maxIndex]]
        while len(newSe):
            tmpSe = []
            for se in newSe:
                lastNode = se[-1]
                lastPreNode = None
                if len(se) > 1:
                    lastPreNode = se[-2]
                if lastPreNode is not None and len(tree[lastNode]) == 1:
                    lineSegments.append(se)
                    continue
                for nextNode in tree[lastNode]:
                    if lastPreNode == nextNode:
                        continue
                    se2 = se.copy()
                    se2.append(nextNode)
                    tmpSe.append(se2)
            newSe = tmpSe
        # print(lineSegments)

        if len(lineSegments) == 1:
            line = lineSegments[0]
            if len(line) % 2 == 0:
                return [len(line) // 2 - 1, len(line) // 2]
            else:
                return [len(line) // 2]
        maxLen = 0
        resultSet = set()
        for i in range(len(lineSegments) - 1, 0, -1):
            n1 = lineSegments[i]
            for j in range(i - 1, -1, -1):
                n2 = lineSegments[j]
                if maxLen > len(n1) + len(n2) - 1:
                    break
                nowLen, nowList = self.getLenAndIndex(n1, n2)
                if nowLen > maxLen:
                    maxLen = nowLen
                    resultSet = set(nowList)
                elif nowLen == maxLen:
                    for node in nowList:
                        resultSet.add(node)
        return list(resultSet)

    def getLenAndIndex(self, n1, n2):
        n3Len = len(n1) + len(n2)
        if len(n1) < len(n2):
            n1, n2 = n2, n1
        commonLen = 0
        for i in range(len(n2)):
            if n1[i] == n2[i]:
                commonLen = i
            else:
                break
        commonLen = commonLen + 1
        # 实际长度
        actLen = n3Len - commonLen*2 + 1
        moveIndex = commonLen - 1 + actLen // 2 - (len(n2) - commonLen)
        if actLen % 2 == 0:
            return actLen, [n1[moveIndex-1], n1[moveIndex]]
        else:
            return actLen, [n1[moveIndex]]


if __name__ == '__main__':
    so = Solution()
    n = 4
    edges = [[1, 0], [1, 2], [1, 3]]
    # n = 9
    #     # edges = [[0,1],[0,2],[2,3],[0,4],[2,5],[5,6],[3,7],[0,8]]
    # n = 6
    # edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
    r = so.findMinHeightTrees(n, edges)
    print(r)
